﻿#include <gtest/gtest.h>

#define MEMSPY_IMPLEMENTATION

#include <xy/utils/memspy.h>
#include <xy/utils/tree.h>

#include <algorithm>
#include <iostream>
#include <random>
#include <set>
#include <vector>

using namespace xy;
using namespace xy::utils;

#define TIMES 100
#define BUF_SIZE 100

TEST(TestTree, bin_tree)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        std::vector<double> arr(BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        tree2<double, void, std::greater<double>> rbt;
        for (int i = 0; i < BUF_SIZE; i++)
            rbt.insert(arr[i]);

        std::sort(arr.begin(), arr.end());
        std::reverse(arr.begin(), arr.end());
        while (!arr.empty())
        {
            EXPECT_DOUBLE_EQ(arr.front(), rbt.min()->value);
            EXPECT_DOUBLE_EQ(arr.back(), rbt.max()->value);
            // if (rbt.Size() < 40)
            //     rbt.draw();

            for (int j = 0; j < arr.size(); j++)
            {
                // 注意这里如果有重复元素，index_of 获得的是第一次出现的位置，因此不比较索引而是直接比较值
                EXPECT_DOUBLE_EQ(arr[j], *(rbt.begin() + j));

                auto node = rbt.find(arr[j]);
                EXPECT_DOUBLE_EQ(arr[j], node->value);
            }

            int j = 0;
            for (auto node : rbt)
            {
                EXPECT_DOUBLE_EQ(arr[j], node);
                j++;
            }

            // 随机删除元素
            int d = rand() % arr.size();
            auto it = arr.begin() + d;
            rbt.remove(*it);
            arr.erase(it);
        }
    }
}

TEST(TestTree, rb_tree)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        std::vector<double> arr(BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        tree_rb<double, std::greater<double>> rbt;
        for (int i = 0; i < BUF_SIZE; i++)
            rbt.insert(arr[i]);

        std::sort(arr.begin(), arr.end());
        std::reverse(arr.begin(), arr.end());
        while (!arr.empty())
        {
            EXPECT_TRUE(rbt.black_height() < (rbt.height() * 2));
            // EXPECT_EQ(arr.size(), rbt.size());
            EXPECT_DOUBLE_EQ(arr.front(), rbt.min()->value);
            EXPECT_DOUBLE_EQ(arr.back(), rbt.max()->value);
            // if (rbt.height() < 4)
            //     rbt.draw();

            for (int j = 0; j < arr.size(); j++)
            {
                auto node = rbt.find(arr[j]);
                EXPECT_DOUBLE_EQ(arr[j], node->value);
            }

            // 随机删除元素
            int d = rand() % arr.size();
            auto it = arr.begin() + d;
            rbt.remove(*it);
            arr.erase(it);
        }
    }
}

TEST(TestTree, interval_tree)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        std::vector<std::tuple<double, double>> arr(BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            double l = u(generator);
            arr[i] = {l, l + u(generator)};
        }

        tree_interval<double> rbt;
        for (int i = 0; i < BUF_SIZE; i++)
            rbt.insert(arr[i]);

        std::sort(arr.begin(), arr.end());
        int countFailed = 0;
        while (!arr.empty())
        {
            EXPECT_TRUE(arr.front() == rbt.min()->value);
            EXPECT_TRUE(arr.back() == rbt.max()->value);
            // if (rbt.Size() < 40)
            //     rbt.draw();

            for (int j = 0; j < arr.size(); j++)
            {
                // 注意这里如果有重复元素，index_of 获得的是第一次出现的位置，因此不比较索引而是直接比较值
                EXPECT_TRUE(arr[j] == *(rbt.begin() + j));

                auto node = rbt.find(arr[j]);
                EXPECT_TRUE(arr[j] == node->value);
            }

            int j = 0;
            for (auto node : rbt)
            {
                EXPECT_TRUE(arr[j] == node);
                j++;
            }

            // 随机生成区间，测试 overlap
            double l = u(generator);
            std::tuple<double, double> interval = {l, l + u(generator)};
            bool overlap = false;
            for (int j = 0; j < arr.size(); j++)
            {
                auto value = arr[j];
                if (std::get<0>(interval) < std::get<0>(value) && std::get<1>(interval) > std::get<0>(value))
                {
                    overlap = true;
                    break;
                }
                if (std::get<0>(interval) < std::get<1>(value) && std::get<1>(interval) > std::get<1>(value))
                {
                    overlap = true;
                    break;
                }
                if (std::get<0>(value) < std::get<0>(interval) && std::get<1>(value) > std::get<0>(interval))
                {
                    overlap = true;
                    break;
                }
                if (std::get<0>(value) < std::get<1>(interval) && std::get<1>(value) > std::get<1>(interval))
                {
                    overlap = true;
                    break;
                }
            }

            auto node = rbt.overlap(interval);
            if (node == rbt.nil())
            {
                EXPECT_FALSE(overlap);
            }
            if (node != rbt.nil())
            {
                EXPECT_TRUE(overlap);
            }

            // 随机删除元素
            int d = rand() % arr.size();
            auto it = arr.begin() + d;
            rbt.remove(*it);
            arr.erase(it);
        }
    }
}

TEST(TestTree, treex)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        // memspy spy;

        std::vector<double> arr(BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        treex<double> rbt;
        auto root = rbt.insert(arr[0]);
        std::vector<decltype(root)> nodes;
        for (int i = 1; i < BUF_SIZE; i++)
        {
            nodes.push_back(rbt.insert(arr[i], root));
            std::shuffle(nodes.begin(), nodes.end(), generator);
            root = nodes.back();
        }
    }
}

TEST(TestTree, list)
{
    memspy spy;
    list<int> l;

    for (int i = 0; i < 10; i++)
    {
        l.insert(i);
    }

    int i = 0;
    for (auto it = l.begin(); it != l.end(); it++)
    {
        EXPECT_EQ(9 - i, *it);
        i++;
    }

    for (int i = 0; i < 10; i++)
    {
        EXPECT_EQ(9 - i, l.root()->value);
        l.remove(l.root());
    }
}

TEST(TestTree, list_remove)
{
    memspy spy;
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        list<double> l;
        std::vector<double> arr(BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
            l.insert(arr[i]);
        }

        while (!arr.empty())
        {
            int d = rand() % arr.size();
            auto it = arr.begin() + d;
            EXPECT_TRUE(l.find(*it) != l.nil());
            l.remove(*it);
            arr.erase(it);
        }
    }
}